beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
#使用这种方式来判断是否是next，容易超时
def is_next(str1,str2):
    str_1_pointer=0
    str_2_pointer=0
    count=0
    while str_1_pointer<len(str1) and str_2_pointer<len(str2):
        if str1[str_1_pointer]!=str2[str_2_pointer]:
            count+=1
        str_1_pointer+=1
        str_2_pointer+=1
    if count==1:
        return True
    else:
        return False

def LadderLenght(beginWord,endWord,wordList):
    if endWord not in wordList:
        return 0
    #状态矩阵
    state=[False for _ in range(len(wordList))]
    queue_List=[]
    grid=[]
    level=1
    have_reach=False
    for i in range(len(wordList)):
        if is_next(beginWord,wordList[i]):
            #如果i可以作为next，则存入到队列中
            queue_List.append(wordList[i])
            state[i]=True
    # print("初始的时候，存入队列的元素：",queue_List)
    # print("下面进行广度优先遍历环节....")
    while queue_List!=[]:
        if have_reach:
            break
        #党queue_List不为空的时候
        #当前轮次中queue_List中的元素数量
        queue_len=len(queue_List)
        # print("本次队列中存在的元素数量：",queue_len)
        # print("本次队列中的元素：",queue_List)
        grid.append(queue_List[:])
        # print(grid)
        level+=1
        while queue_len>0:
            #弹出队列中第一个元素
            str_1=queue_List.pop(0)
            # print("取出元素：",str_1)
            if str_1==endWord:
                have_reach=True
                break
            for i in range(len(wordList)):
                if is_next(str_1,wordList[i]) and state[i]==False and wordList[i] not in queue_List:
                    queue_List.append(wordList[i])
            queue_len-=1
    if have_reach:
        return level
    else:
        return 0
print(LadderLenght(beginWord,endWord,wordList))